package com.chenxys.algorithm.newbie;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 *      通过链表实现队列
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/27/23 11:58 PM
 * @Copyright ©
 */
@SuppressWarnings("all")
public class QueueByList {
    /**
     * <p>
     *     队列节点的数据结构
     * </p>
     * @param <V>
     */
    public static class Node<V> {
        public V value;
        public Node<V> next;

        public Node(V value) {
            this.value = value;
            this.next = null;
        }
    }

    /**
     * <p>
     *     使用链表实现队列
     * </p>
     * @param <V>
     */
    public static class MyQueue<V> {
        // 队列头指针 指向队列头
        private Node<V> head;
        // 队列尾指针 指向队列尾
        private Node<V> tail;
        // 队列大小
        private int size;

        // 初始化时全部为空
        public MyQueue() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        // 判断当前队列是否为空
        public boolean isEmpty() {
            return size == 0;
        }

        // 获取当前队列大小
        public int size() {
            return size;
        }

        /**
         * <p>
         *     将某个值加入到队列中
         * </p>
         * @param value 值/元素
         */
        public void offer(V value) {
            // 新建节点保存元素
            Node<V> cur = new Node<>(value);
            // 如果尾指针为空，则将当前节点设置为头节点和尾节点
            if (tail == null) {
                head = cur;
                tail = cur;
            } else { // 否则，将尾巴节点的下一个节点设置为当前节点，并将当前节点赋值给尾节点
                tail.next = cur;
                tail = cur;
            }
            // 队列长度+1
            size++;
        }

        /**
         * <p>
         *     从队列中弹出元素
         * </p>
         * @return 元素
         */
        public V poll(){
            V ans = null;
            // 如果头指针不为空,则将头指针指向的节点的值赋值给ans,并将头指针向下移动,队列长度-1
            if (head != null){
                ans = head.value;
                head = head.next;
                size--;
            }
            // 如果头指针为空,则将尾指针也指向空,避免脏数据
            if (head == null) {
                tail = null;
            }
            return ans;
        }

        /**
         * <p>
         *     获取队列中元素的值,但是不删除
         * </p>
         */
        public V peek() {
            V ans = null;
            if (head != null){
                ans = head.value;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        MyQueue<Integer> myQueue = new MyQueue<>();
        Queue<Integer> test = new LinkedList<>();
        int testTimes = 5000000;
        int maxValue = 20000000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            if (myQueue.isEmpty() != test.isEmpty()) System.out.println("Oops!");
            if (myQueue.size() != test.size()) System.out.println("Oops!");
            double decide = Math.random();
            if (decide < 0.33){
                int num = (int) (Math.random() * maxValue);
                myQueue.offer(num);
                test.offer(num);
            } else if (decide < 0.66){
                if (!myQueue.isEmpty()) {
                    int num1 = myQueue.poll();
                    int num2 = test.poll();
                    if (num1 != num2) System.out.println("Oops!");
                }
            } else {
                if (!myQueue.isEmpty()){
                    int num1 = myQueue.peek();
                    int num2 = test.peek();
                    if (num1 != num2) System.out.println("Oops!");
                }
            }
        }
        System.out.println("Test Finish!");
    }
}
